/*
 * @lc app=leetcode.cn id=10 lang=cpp
 *
 * [10] 正则表达式匹配
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
  bool isMatch(const string &s, const string &p, int inx_s, int inx_p) {

    if (inx_p == p.size()) {
      return inx_s == s.size();
    }

    if (inx_s == s.size()) {
      if (inx_p == p.size()) {
        return true;
      }
      if((p.size() - inx_p) % 2)
      {
        if(p[inx_p] == '*') ++inx_p;
        else return false;
      }
      while(inx_p < p.size() && p[inx_p+1] == '*')
      {
        inx_p += 2;
      }
      return inx_p == p.size();
    }

    switch (p[inx_p]) {
    case '.': {
      if (inx_p < p.size() - 1 && p[inx_p + 1] == '*') {
        return isMatch(s, p, inx_s, inx_p + 2) ||
               isMatch(s, p, inx_s + 1, inx_p + 1);
      } else
        return isMatch(s, p, inx_s + 1, inx_p + 1);
      break;
    }

    case '*': {
      if (inx_p == 0) {
        return isMatch(s, p, inx_s, inx_p + 1);
      }
      if (p[inx_p - 1] == '.' || (p[inx_p - 1] == s[inx_s])) {
        return isMatch(s, p, inx_s + 1, inx_p) ||
               isMatch(s, p, inx_s + 1, inx_p + 1) ||
               isMatch(s, p, inx_s, inx_p + 1);
      }
      if (p[inx_p - 1] != s[inx_s]) {
        return isMatch(s, p, inx_s, inx_p + 1);
      }
      return false;
      break;
    }

    default: {
      if (p[inx_p] != s[inx_s]) {
        if (inx_p < p.size() - 1 && p[inx_p + 1] == '*') {
          return isMatch(s, p, inx_s, inx_p + 2);
        }
        return false;
      } else {
        if (inx_p < p.size() - 1 && p[inx_p + 1] == '*') {
          return isMatch(s, p, inx_s, inx_p + 2) ||
                 isMatch(s, p, inx_s + 1, inx_p + 1);
        }
        return isMatch(s, p, inx_s + 1, inx_p + 1);
      }
      break;
    }
    }

    return false;
  }
  bool isMatch(string s, string p) {
    int pos = p.npos;
    while ((pos = p.find("**")) != p.npos) {
      p.erase(pos, 1);
    }
    return isMatch(s, p, 0, 0);
  }
};
// @lc code=end
